"""
直接插入排序算法思想：将数组分为有序部分和无序部分，每次从无序部分取一个元素，插入到有序部分的合适位置，使有序部分始终保持有序(且有序部分的元素数量不断增加)。
代码解释：
外层循环从索引1开始（默认索引0的元素已排序）。
key保存当前待插入的元素，j指向有序部分的最后一个元素。
内层循环通过比较将有序部分中大于key的元素依次后移，为key腾出插入位置。
最后将key插入到j+1的位置（此时arr[j] <= key或j=-1）。
时间复杂度：最好情况（有序）为O(n)，最坏情况和平均情况为O(n²)。
"""


def insertion_sort(arr):
    # 从第二个元素开始（第一个元素视为已排序）
    for i in range(1, len(arr)):
        # 保存当前要插入的元素 因为后面可能会被覆盖
        key = arr[i]
        # 有序部分的最后一个元素索引
        j = i - 1
        # 在有序部分中找到插入位置
        # 若有序元素大于key，将其向后移动
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        # 将key插入到正确位置
        arr[j + 1] = key
    return arr


# 测试
arr = [12, 11, 13, 5, 6]
sorted_arr = insertion_sort(arr)
print("直接插入排序结果:", sorted_arr)  # 输出: [5, 6, 11, 12, 13]
